package com.lw.leetcode.dp.b;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 1959. K 次调整数组大小浪费的最小总空间
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/24 17:07
 */
public class MinSpaceWastedKResizing {

    public static void main(String[] args) {
        MinSpaceWastedKResizing test = new MinSpaceWastedKResizing();

        // 10
//        int[] arr = {10, 20};
//        int k = 0;

        // 10
//        int[] arr = {10, 20, 30};
//        int k = 1;

        // 15
//        int[] arr = {10, 20, 15, 30, 20};
//        int k = 2;

        // 15
        int[] arr = Utils.getArr(200, 1, 100000);
        int k = 199;
        System.out.println(k);

        int i = test.minSpaceWastedKResizing(arr, k);
        System.out.println(i);
    }

    public int minSpaceWastedKResizing(int[] nums, int k) {
        int length = nums.length;
        int[][] arr = new int[length][k + 1];
        int max = 0;
        int m = nums[0];
        for (int i = 1; i < length; i++) {
            int v = nums[i];
            max = Math.max(max, v);
            arr[i][0] = 11;
            if (v >= m) {
                arr[i][0] = arr[i - 1][0] + i * (v - m);
                m = v;
            } else {
                arr[i][0] = arr[i - 1][0] + m - v;
            }
            for (int j = 1; j <= k; j++) {
                int item = arr[i - 1][j - 1];
                int s = 0;
                int t = v;
                for (int n = i - 1; n >= j; n--) {
                    int v1 = nums[n];
                    if (t >= v1) {
                        s += (t - v1);
                    } else {
                        s += (i - n) * (v1 - t);
                        t = v1;
                    }
                    item = Math.min(item, s + arr[n - 1][j - 1]);
                }
                arr[i][j] = item;
            }
        }
        return arr[length - 1][k];
    }

}
